1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
| #include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:10240000000,10240000000") #define inf 0x3ffffff #define mem(x,y) memset(x,y,sizeof(x)) #define mec(x,y) memcpy(x,y,sizeof(x)) #define debug puts("============") #define eps 1e-5 #define mp(x,y) make_pair(x,y) #define nit int #define mian main #define ture true #define ll long long #define maxn 100+4 #define sf(x) scanf("%d",&x) #define sff(x,y) scanf("%d%d",&x,&y) #define sfff(x,y,z) scanf("%d%d%d",&x,&y,&z) #define NE 2000000 #define NV 10000 const int mx=50010; int c[mx]; int len[mx],l[mx],r[mx],fa[mx]; int n,m,R; #define inf 0xfffffff #define mem(x,y) memset(x,y,sizeof(x)) int cmp(int x,int y) { return len[x]>len[y]; } int findf(int x) { return x==fa[x]?x:fa[x]=findf(fa[x]); } int kruskal() { int res=0; for(int i=0;i<=n+m;i++)fa[i]=i; for(int i=0;i<R;i++)c[i]=i; sort(c,c+R,cmp); for(int i=0;i<R;i++) { int t=c[i]; int a=findf(l[t]),b=findf(r[t]); if(a!=b) res+=len[t],fa[a]=b; } return 10000*(n+m)-res; } int main() { int t; scanf("%d",&t); while(t--) { sfff(n,m,R); int x,y,z; for(int i=0;i<R;i++) { sfff(x,y,z); l[i]=x,r[i]=y+n,len[i]=z; } printf("%d\n",kruskal()); } }
|